using System;
using System.Collections.Generic;
using System.Text;

namespace TestGraphCut
{
    class node : IComparable<node>
    {
        public int name;
        public int tree;
        public node parent; //reference type
        public int CompareTo(node other)
        {
            return name.CompareTo(other.name);
        }

    }

    class edge : IComparable<edge>
    {
        public node terminal1; //reference type
        public node terminal2; //reference type
        public int capacity;
        public int CompareTo(edge other)
        {
            if ((other.terminal1 == this.terminal1) && (other.terminal2 == this.terminal2) || (other.terminal2 == this.terminal1) && (other.terminal1 == this.terminal2))
                return 0;
            return 1;
        }
    }

    class GraphCut
    {
        List<node> Slist = new List<node>();
        List<node> Tlist = new List<node>();
        List<node> Alist = new List<node>();
        Queue<node> queO = new Queue<node>();
        List<node> nodes;
        List<edge> edges;
        node S;
        node T; 
        List<node> Stree = new List<node>();
        List<node> Ttree = new List<node>();

        public GraphCut(List<node> nodes, List<edge> edges, node S, node T)
        {
            this.edges = edges;
            this.nodes = nodes;
            this.S = S;
            this.T = T;
            Slist.Add(S);
            Tlist.Add(T);
            Alist.Add(S);
            Alist.Add(T);
           
        }

        void group()
        {
            foreach (node p in nodes)
            {
                if (p.tree == 1)
                    Stree.Add(p);
                else
                    Ttree.Add(p);
            }

        }

        public List<node> getStree()
        {
            return Stree;
        }

        public List<node> getTtree()
        {
            return Ttree;
        }

        public void doCut()
        {
            while (true)
            {
                List<node> pathnode;
                pathnode = grow();
                if (pathnode.Count == 0)
                    break;
                augument(pathnode);
                adopt();

            }

        }

        List<node> grow()
        {
            List<node> PathNodes = new List<node>();
            while (Alist.Count > 0)
            {
                node p;
                p = Alist[0];

                List<node> neighbour = new List<node>();
                neighbour = this.findNeighbours(p);
                foreach (node q in neighbour)
                {
                    if (q.tree == 0)
                    {
                        q.tree = p.tree;
                        q.parent = p;
                        Alist.Add(q);
                    }
                    if (q.tree != 0 && q.tree != p.tree)
                    {
                        PathNodes.Add(p);
                        PathNodes.Add(q);
                        return PathNodes;
                    }
                }
                Alist.Remove(p);
            }
            return PathNodes;
        }

        List<edge> findPath(List<node> pathNodes)
        {
            List<edge> path = new List<edge>();
            foreach (edge e in edges)
            {
                if ((e.terminal1 == pathNodes[0] && e.terminal2 == pathNodes[1]) || (e.terminal2 == pathNodes[0] && e.terminal1 == pathNodes[1]))
                {
                    path.Add(e);
                    break;
                }
            }

            foreach (node p in pathNodes)
            {
                node temp = p;
                node parent;

                    while (!(temp.name == -1000 || temp.name == -2000))
                    {
                        parent = temp.parent;
                        foreach (edge e in edges)
                        {
                            if ((e.terminal1 == temp && e.terminal2 == parent) || (e.terminal2 == temp && e.terminal1 == parent))
                            {
                                path.Add(e);
                                break;
                            }
                        }
                        temp = parent;
                    }
                }
            
            return path;
        }

        void updateCapacity(int miniCapacity, List<edge> path)
        {
            foreach (edge e in path)
            {
                foreach (edge MapEdge in this.edges)
                {
                    if (MapEdge.CompareTo(e) == 0)
                        MapEdge.capacity -= miniCapacity;
                }
            }
        }


        void augument(List<node> pathNodes)
        {
            List<edge> path = new List<edge>();
            path = this.findPath(pathNodes);
            int miniCapacity = int.MaxValue;
            foreach (edge e in path)
            {
                if (e.capacity < miniCapacity)
                    miniCapacity = e.capacity;
            }
            this.updateCapacity(miniCapacity, path);
            foreach (edge e in path)
            {
                if (e.terminal1.tree == e.terminal2.tree)
                {
                    if (e.terminal1.parent == e.terminal2)
                    {
                        e.terminal1.parent = null;
                        if (!queO.Contains(e.terminal1))
                            queO.Enqueue(e.terminal1);
                    }
                    else
                    {
                        e.terminal2.parent = null;
                        if (!queO.Contains(e.terminal2))
                            queO.Enqueue(e.terminal2);
                    }

                }
            }


        }

        List<node> findNeighbours(node p)
        {
            List<node> neighbour = new List<node>();
            foreach (edge e in this.edges)
            {
                if (e.terminal1 == p && e.capacity > 0)
                {
                    if (!neighbour.Contains(e.terminal2))
                        neighbour.Add(e.terminal2);
                }
                if (e.terminal2 == p && e.capacity > 0)
                {
                    if (!neighbour.Contains(e.terminal1))
                        neighbour.Add(e.terminal1);
                }
            }
            return neighbour;

        }

        List<node> findZeroCapNei(node p)
        {
            List<node> neighbour = new List<node>();
            foreach (edge e in this.edges)
            {
                if (e.terminal1 == p && e.capacity == 0)
                {
                    if (!neighbour.Contains(e.terminal2))
                        neighbour.Add(e.terminal2);
                }
                if (e.terminal2 == p && e.capacity == 0)
                {
                    if (!neighbour.Contains(e.terminal1))
                        neighbour.Add(e.terminal1);
                }
            }
            return neighbour;
        }



        void adopt()
        {
            while (queO.Count > 0)
            {
                node p;
                p = queO.Dequeue();
                List<node> neighbour;
                neighbour = this.findNeighbours(p);
                bool hasParent = false;
                for (int i = 0; i < neighbour.Count; i++)
                {
                    node q = neighbour[i];
                    if (q.tree == p.tree)
                    {
                        bool done = false;
                        node temp = q;
                        while (true)
                        {
                            if (temp.name == -1000 || temp.name == -2000)
                            {
                                done = true;
                                break;
                            }
                            if (temp.parent == null)
                                break;
                            temp = temp.parent;
                        }
                        if (done)
                        {
                            hasParent = true;
                            p.parent = q;
                            break;
                        }
                    }
                }
                if (!hasParent)
                {
                    List<node> nghbs = this.findNeighbours(p);
                    foreach (node q in nghbs)
                    {
                        if (q.tree == p.tree)
                            Alist.Add(q);
                        if (q.parent == p)
                        {
                            queO.Enqueue(q);
                            q.parent = null;
                        }
                    }
                    nghbs.Clear();
                    nghbs = this.findZeroCapNei(p);
                    foreach (node q in nghbs)
                    {
                        if (q.parent == p)
                        {
                            queO.Enqueue(q);
                            q.parent = null;
                        }

                    }
                    p.tree = 0;
                    Alist.Remove(p);

                }


            }
        }


    }
    
    class Program
    {
        static void Main(string[] args)
        {
            List<node> nodelist = new List<node>();
            List<edge> edgelist = new List<edge>();
            node n1 = new node();
            node n2 = new node();
            node n3 = new node();
            n1.name = 1;
            n2.name = 2;
            n3.name = 3;
            n1.tree = n2.tree = n3.tree = 0;
            nodelist.Add(n1);
            nodelist.Add(n2);
            nodelist.Add(n3);

            edge e1 = new edge();
            edge e2 = new edge();
            edge e3 = new edge();
            edge e4 = new edge();
            edge e5= new edge();
            edge e6 = new edge();
            edge e7 = new edge();
            edge e8 = new edge();
            


            node S = new node();
            node T = new node();

            e1.terminal1 = S;
            e1.terminal2 = n1;
            e1.capacity = int.MaxValue;

            e2.terminal1 = S;
            e2.terminal2 = n2;
            e2.capacity = 100;

            e3.terminal1 = S;
            e3.terminal2 = n3;
            e3.capacity = 0;

            e4.terminal1 = T;
            e4.terminal2 = n1;
            e4.capacity =0;

            e5.terminal1 = T;
            e5.terminal2 = n2;
            e5.capacity = 200;

            e6.terminal1 = T;
            e6.terminal2 = n3;
            e6.capacity = int.MaxValue;

            e7.terminal1 = n2;
            e7.terminal2 = n1;
            e7.capacity = 300;

            e8.terminal1 = n2;
            e8.terminal2 = n3;
            e8.capacity = 500;

            S.name=-1000;
            T.name=-2000;
            S.tree = 1;
            T.tree = 2;

            edgelist.Add(e1);
            edgelist.Add(e2);
            edgelist.Add(e3);
            edgelist.Add(e4);
            edgelist.Add(e5);
            edgelist.Add(e6);
            edgelist.Add(e7);
            edgelist.Add(e8);

            GraphCut gc = new GraphCut(nodelist, edgelist, S, T);
            gc.doCut();

        }
    }
}
